package bin_tree.sort;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * 七大排序
 */
public class SevenSort {
    private static final ThreadLocalRandom random = ThreadLocalRandom.current();
    /**
     * 将任意数组进行原地堆排序
     * @param arr
     */
    public static void heapSort(int[] arr){
        //将任意数组调整为最大堆
        //从最后一个非叶子节点开始
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        //依次取出堆顶元素和最后位置元素交换
        //最开始待排序[0,arr.length-1] 已排序[]
        //第一次排序 待排序[0,arr.length-2] 已排序[arr.length-1]
        //第二次排序 待排序[0,arr.length-3]  已排序[arr.length-2,arr.length-1]
        //此处终止条件不用写i=0,当整个待排序数组就剩一个元素时，其实整个数组已经有序
        for (int i = arr.length-1; i >0 ; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    /**
     * 冒泡排序
     * @param arr
     */
    public static void bubbleSort(int[] arr){
        //最外层表示要比较的趟数，此处-1是因为，整个待排序数组剩一个元素时，整个数组已经有序
        for (int i = 0; i < arr.length-1; i++) {
            boolean isSwapped=false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    isSwapped=true;
                    swap(arr,j,j+1);
                }
            }
            if(!isSwapped){
                //内层循环没有元素交换，整个数组有序
                break;
            }
        }
    }


    /**
     * 直接选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        // 每次从待排序数组中选择最小值放在待排序数组的最前面。
        // 最外层的for循环表示要执行的总次数，类似于冒泡，当剩下最后一趟时，整个数组已经有序
        // 默认第一个元素就是有序的
        // 已经有序的集合[0,i)
        // 待排序的集合[i + 1,n)
        // 每次进行一趟排序，最小值就放在了数组的最前面，已经有序的集合元素个数 + 1
        // 待排序集合元素个数 - 1
        for (int i = 0; i < arr.length - 1; i++) {
            // min变量存储了最小值元素的下标
            int min = i;
            // 每次从无序区间中选择最小值
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 此时min就存储了最小值的元素下标，就把min对应的元素换到无序区间的最前面
            swap(arr,i,min);
        }
    }

    /**
     * 双向选择排序，每次选出最小值放前面，最大值放后面
     * @param arr
     */
    public static void selectSortOP(int[] arr) {
        int low = 0,high = arr.length - 1;
        // 有序区间[0,low + 1)
        while (low < high) {
            int min = low,max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] > arr[max]) {
                    max = i;
                }
                if (arr[i] < arr[min]) {
                    min = i;
                }
            }
            // min存储了无序区间的最小值，max存储了无序区间的最大值
            swap(arr,low,min);
            if (max == low) {
                // 当max就处在low位置，由于swap(arr,low,min),low对应的元素值修改了，修改到min对应的下标
                max = min;
            }
            swap(arr,max,high);
            low += 1;
            high -= 1;
        }
    }


    /**
     * 直接插入排序
     * @param arr
     */
    public static void insertSort(int[] arr){
        //有序数组[0，i)
        //默认第一个就是有序
        for (int i = 1; i <arr.length ; i++) {
            //每次都从无序区间中选择第一个元素插入到有序区间的合适位置
            for (int j = i; j >0 &&arr[j-1]>arr[j] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }

    /**
     * 在数组arr[l...r]上使用插入排序
     * @param arr
     * @param l
     * @param r
     */
    public static void insertBase(int[] arr,int l,int r){
        //有序区间[l,i)
        //无序区间[i，r]
        for (int i = l+1 ;i <=r ; i++) {
            for (int j = i; j >l && arr[j-1]>arr[j] ; j--) {
                swap(arr,j,j-1);
            }
        }
    }

    /**
     * 折半插入排序
     */
    public static void bsInsertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int val=arr[i];
            int low=0;
            int high=i;
            while (low<high) {
                int mid = (low + high) / 2;
                if (val >=arr[mid]) {//保证了稳定性
                    low=mid+1;
                } else {
                    high=mid;
                }
            }
            //数据搬移
            for (int j = i; j > low; j--) {
                arr[j]=arr[j-1];
            }
            //low就是元素插入位置
            arr[low]=val;

        }
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void shellSort(int[] arr){
        int gap=arr.length/2;
        while (gap>=1){
            insertionSortGap(arr,gap);
            gap = gap / 2;
        }
    }

    private static void insertionSortGap(int[] arr, int gap) {
        //不断从gap开始走到数组末尾
        for (int i = gap; i <arr.length ; i++) {
            //最内层从gap索引开始向前看，看的元素就是距离gap长度的元素
            // 不断比较当前元素和前面gap元素大小
            // j - gap >= 0说明前面数组还要相同距离的元素，比较arr[j] 和 arr[j - gap]
            for (int j = i; j - gap >= 0 &&arr[j] <arr[j-gap]; j=j-gap) {
                swap(arr, j, j-gap);
            }
        }
    }

    /**
     * 在arr上进行归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr){
        mergeSortInternal(arr,0,arr.length-1);
    }

    /**
     * 递归
     * 在arr[l...r]上进行归并排序
     * @param arr
     * @param l
     * @param r
     */
    private static void mergeSortInternal(int[] arr, int l, int r) {
        if(r-l<=15){
            insertBase(arr,l,r);
            return;
        }
        int mid=l+((r-l)>>1);
        mergeSortInternal(arr,l,mid);//先对左半部分进行归并排序
        mergeSortInternal(arr,mid+1,r);//再对右半部分进行归并排序
        if(arr[mid]>arr[mid+1]){
            merge(arr,l,mid,r);
        }
    }

    /**
     * 将已经有序的arr[l..mid]和[mid+1...r]合并为一个大的有序数组
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        //开辟一个大小和合并后数组大小相同的数组
        int[] temp=new int[r-l+1];
        //将原数组的内容拷贝到新数组
        for (int i = l; i <=r; i++) {
            temp[i-l]=arr[i];
        }
        int i=l;//左半有序数组的第一个元素
        int j=mid+1;//右半有序数组第一个元素
        //遍历原数组，选择左半区间和右半区间的最小值写回原数组
        //k表示当前处理到原数组的哪个位置
        for (int k = l; k <=r ; k++) {
            if(i>mid){
                //此时左半区间处理完毕，将右区间剩下的元素写回原数组
                arr[k]=temp[j-l];
                j++;
            }else if(j>r){
                //此时有右半区间处理完毕，将左区间剩下的元素写回原数组
                arr[k]=temp[i-l];
                i++;
            }else if(temp[i-l]<temp[j-l]){
                arr[k]=temp[i-l];
                i++;
            }else {
                arr[k]=temp[j-l];
                j++;
            }
        }
    }

    /**
     * 归并排序的非递归写法
     * @param arr
     */
    public static void mergeSortNonRecursion(int[] arr){
        //sz表示每次合并的个数，最开始从1个元素开始合并，以此累乘
        for (int sz = 1; sz <= arr.length ; sz=sz*2) {
            //merge过程，i表示每次merge开始的索引下标
            for (int i = 0; i+sz <arr.length ; i+=sz*2) {
                //left=i
                //mid=left+sz-1;
                //right=mid+sz=left+2*sz-1
                merge(arr,i,i+sz-1,Math.min(i+2*sz-1, arr.length-1));
            }
        }
    }

    /**
     * 快排的基础实现
     * @param arr
     */
    public static void quickSort(int[] arr){
        quickSortInternal(arr,0,arr.length-1);
    }

    /**
     * 在l...r进行快排
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if(r-l<=15){
            insertBase(arr,l,r);
            return;
        }
        //求基准值
        int p=partition(arr,l,r);
        quickSortInternal(arr,l,p-1);
        quickSortInternal(arr,p+1,r);
    }

    private static int partition(int[] arr, int l, int r) {
        //选择第一个元素作为基准值
//        int v=arr[l];
        //在当前数组中随机选择一个元素作为基准值
        int randomIndex=random.nextInt(l,r);
        swap(arr,l,randomIndex);
        int v=arr[l];
        int j=l;
        //i是当前处理的元素下标
        //arr[l+1...j]<v
        //arr[j+1...i]>=v
        for (int i = l+1; i <=r ; i++) {
            if(arr[i]<v){
                swap(arr,j+1,i);
                //小于v的元素+1
                j++;
            }
        }
        swap(arr,j,l);
        return j;
    }

    /**
     * 二路快排 （将重复元素放在左右两部分，使两部分平衡）
     * @param arr
     */
    public static void quickSort2(int[] arr){
        quickSortInternal2(arr,0,arr.length-1);
    }

    private static void quickSortInternal2(int[] arr, int l, int r) {
        if(r-l<=15){
            insertBase(arr,l,r);
            return;
        }
        int p=partition2(arr,l,r);
        quickSortInternal2(arr,l,p+1);
        quickSortInternal2(arr,p+1,r);

    }

    private static int partition2(int[] arr, int l, int r) {
        int randomIndex=random.nextInt(l,r);
        swap(arr,randomIndex,l);
        int v=arr[l];
        //arr[l+1...i)<v
        int i=l+1;
        //arr(j...r]>v
        int j=r;
        while (true){
            while (i<=r && arr[i]<v){
                i++;
            }
            while (j>=l+1 && arr[j]>v){
                j--;
            }
            if(i>j){
                break;
            }
            swap(arr,i,j);
            i++;
            j--;
        }
        swap(arr,l,j);
        return j;
    }


    /**
     * 三路快排（一次性将重复元素放到最终位置）
     * @param arr
     */
    public static void quickSort3(int[] arr){
        quickSortInternal3(arr,0,arr.length-1);
    }

    private static void quickSortInternal3(int[] arr, int l, int r) {
        if(r-l<=15){
            insertBase(arr,l,r);
            return;
        }
        //partition部分
        int randomIndex=random.nextInt(l,r);
        swap(arr,randomIndex,l);
        int v=arr[l];
        //arr[l+1...lt]<v
        int lt=l;
        //arr[gt...r]>v
        int gt=r+1;
        //arr[lt+1...i)==v
        int i=l+1;
      //终止条件i==gt
        while (i<gt){
            if(arr[i]<v){
                swap(arr,lt+1,i);
                i++;
                lt++;
            }else if(arr[i]==v){
                i++;
            }else {
                swap(arr,gt-1,i);
                gt--;
                //此时i不需要++，因为gt-1这个元素还没有处理，刚好换到i这个位置继续处理
            }
        }
        swap(arr,l,lt);
        //arr[l...lt-1]<v
        quickSortInternal3(arr,l,lt-1);
        //arr[gt...r]>v
        quickSortInternal3(arr,gt,r);
    }

    /**
     * 计数排序
     * 一般适用于有n个数，数据范围是0-n之间的
     * @param arr
     */
    public static void countingSort(int[] arr){
        int minVal=arr[0];
        int maxVal=arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]<minVal){
                minVal=arr[i];
            }
            if(arr[i]>maxVal){
                maxVal=arr[i];
            }
        }
        int[] count=new int[maxVal-minVal+1];
        for(int i=0;i<arr.length;i++){
            count[arr[i]-minVal]++;
        }

        //说明，在计数数组中，已经把arr数组当中每个数据出现的次数都已经统计好了
        //接下来，只需要遍历计数数组，把数据写回arr
        int indexArray=0;
        for (int i = 0; i < count.length; i++) {
            while(count[i]>0){
                //这里一定要加minval，因为不一定就是i出现了count[i]
                arr[indexArray]=i+minVal;
                count[i]--;//数量-1
                indexArray++;//下标要向后移动
            }
        }
    }

    /**
     * 元素的下沉操作
     * @param arr
     * @param i
     * @param n 当前arr中有效的元素个数
     */
    private static void siftDown(int[] arr, int i, int n) {
        while((i*2)+1<n){
            int j=(i*2+1);
            if(j+1<n && arr[j+1]>arr[j]){
                j=j+1;
            }
            if(arr[i]>=arr[j]){
                break;
            }else {
                swap(arr,i,j);
                i=j;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
}
